\documentclass{elsart}
%\documentclass[10pt, a4paper, twoside, final, onecolumn]{icton2010}
%\documentclass[10pt, draftcls, onecolumn] {IEEEtran}
%\documentclass[12pt,a4paper]{article}
%\textwidth 16.0 cm
%\textheight 24.7 cm
%\IEEEoverridecommandlockouts \overrideIEEEmargins
\usepackage{amsmath}
\usepackage{epsfig}
%\interdisplaylinepenalty=2500
\usepackage{array}
\usepackage{placeins}
\usepackage{url}
\usepackage{enumerate}
\usepackage[centerlast]{caption}
%\usepackage{listings}
\usepackage{cite}
\usepackage{pslatex}
% \newif\iflong\longfalse
\usepackage[pdftex]{hyperref}  % so we  can generate nice pdf
\hypersetup{pdftex,
            backref=true,
            hyperindex=true,
            colorlinks=true,
            linkcolor=black,citecolor=black,filecolor=black,urlcolor=black,
            bookmarks=true,
            breaklinks=true
            }
\usepackage{graphicx}
\usepackage{url}
%\pagestyle{empty}

\begin{document}



\begin{frontmatter}
\title{\bf Optimization of Multi-Layered Telecommunications Networks}
\author{
Ronald G. Addie$^1$, David Fatseas$^1$ and Moshe
Zukerman$^2$
}
\maketitle
\address{
1.~Department of Mathematics and Computing, University of Southern
Queensland, Australia, Tel +61 7 46 31 5520, Fax: +61 76 46 31 5550 {\tt addie@usq.edu.au, david\_fatseas@yahoo.com}.
\\ 2. ~ Electronic Engineering Department, City University of Hong Kong,
Hong Kong SAR, {\tt m.zu@cityu.edu.hk}}
\date{\today}
%\thispagestyle{empty}

\begin{abstract}

\noindent Data transported on the Internet is handled by various technologies at different layers.
The move towards an optically transparent internet will accelerate when it is
justified by the cost structure of the various technologies.
In this paper we describe a unified optimization framework for multiple
technologies that interwork together based on the following assumptions:
(i) every layer is associated with a unique technology,
(ii) traffic can be modeled as a Poisson stream of {\em flows},
(iii) a flow will be served by a layer (technology) on a least-cost basis.
This way traffic is split between the layers and if, under a given cost structure,
a layer (e.g. IP) is found to have no ``customers'' (flows) because
it is too costly relative to other layers (e.g. WDM), it will be excluded.
In addition to technology choices we also optimize link dimensioning and virtual topology.
\end{abstract}

\begin{keyword} network optimization, traffic engineering, network evolution, layered architecture, traffic modeling.
\end{keyword}

\end{frontmatter}

\section{Introduction}

\noindent The currently evolved Internet architecture is based on a
variety of technologies and serves numerous services and traffic
types. Internet design that will minimize cost subject to meeting
quality of service (QoS) requirements of the various services
requires simultaneous optimization of many aspects, such as,
technology choices, virtual topology, routing, and traffic grooming.
It is clear that optimizing the entire Internet from all these
aspects is too difficult given its size, the multiple domains, the
wide range of technology options and the unpredictable and complex
nature of the traffic.

 There are many papers which propose mathematical programming
formulations for network design (e.g. \cite{Ramaswami96design,RefWorks:3863,RefWorks:3797,}) however
these are applicable only to relatively
small networks and only consider a subset of the
above problems. This limitation is also applicable to certain heuristics that
have been proposed (e.g. \cite{Zhu02Traffic,Sridharan02Practical,RefWorks:3863}), that are not
scalable to large problems. Furthermore, when a large number of technologies are
considered simultaneously, formulation of the design problem as a
mathematical program is a
task of massive complexity, and its solution, if it can be obtained,
cannot be intuitively understood.

The book \cite{Zhu05Traffic} analyses {\em traffic grooming} in
a multi-layered network (or a multi-layered graph). This is very closely
related to the present work, however, our objective includes technology choices, and
link capacity dimensioning as part of the problem, whereas \cite{Zhu05Traffic}
assumes that the link capacities are given, and a specific collection of
grooming technologies is available, so the task to be solved is how to
route traffic through this network. Also, we consider a statistical
model of traffic adopting a Pareto distribution for flow sizes, whereas
\cite{Zhu05Traffic} analyses a scenario, in which a given
series of flows are to be serviced by a network, rather than a statistical model
in which the specific flows are not known, but rather we assume that
we know the overall statistics of these flows.

The objective of \cite{Zhu05Traffic} is to identify the best strategy for
servicing a sequence of demands offered to a given network, whereas the objective
we are concerned with is, given a statistical description of the flows that
a network is to carry, what technology layers, what routing  strategies
should be adopted, and what link capacities will then be required, in order
to satisfy the demands placed on the network (except with a low probability)
at least cost.

\subsection{A Unified Layered Routing Model}

 We propose and develop a unified framework for multiple technologies that interwork together under realistic assumptions of traffic demands. To do this we adopt a model based on the following principles: (i) each layer is associated with a unique technology (e.g. IP, ATM, WDM, or a specific grooming technique); (ii) traffic can be modelled as a Poisson stream of independently distributed\textit{ flows}; and (iii) each flow is routed on the least-cost path\textit{ for this flow size} in each layer (technology). Each layer provides the ``service'' of passing a request from the layer above directly to the layer below. Sometimes this is the cheapest way to fulfil a service request. Hence, adopting least-cost paths in each layer ensures that the least-cost technology will be used.

 A new technology can be incorporated into this model by choosing a collection of parameters which determine, for each layer, what it will cost to deliver a certain type of traffic and how traffic will be {\em split} between layers when there is a choice. Each layer is a network in its own right, and the links of layer $n+{\rm 1}$ correspond to the traffic streams of layer $n$. We then use shortest-path routing as the design principle for each layer, so the design of each layer is {\em almost} independent from the design of other layers.

 However, since the cost of links in layer $n+{\rm 1}$ is determined by the cost of the whole path that these links follow, in layer $n$, the traffic in layer $n+{\rm 1}$ will change with the costs in layer $n$, and this will cause the traffic in layer $n$ to change and hence the costs in layer $n$ will change again. An iterative repeat substitution scheme for designing all the layers converges quickly, in our experiments, although the experiments are at an early stage.

\subsection{Layered Routing}

 We assume that all nodes are {\em capable} of the switching and routing of all the layers,
i.e. each node is equipped with all technologies. Physical
transmission occurs only at layer 0. Links at higher layers are
composed of paths through the layer beneath. Any path, between any pair of nodes in
layer $k$, is a possible link in layer $n>k$, however in many cases it will transpire
(for reasons of cost) that a given pair is not connected. Every layer provides,
as a bare minimum, the service of merely providing access to the links of the layer
below, at no extra cost. If this is the only function provided in a certain layer
after the optimization algorithm has completed its work, this means that it has been determined that the technology corresponding to this layer is not cost effective and will not be used. For example, due to the excessive cost of handling individual packets in the IP layer \cite{RefWorks:3370}, it might be more cost effective to delegate switching (possibly optical switching) to lower layers under a given future cost structure.

\subsection{Cost of Communication and Flows}

 Internet cost can be classified into three categories:

\begin{enumerate}
\item  Data processing: in the IP layer this category includes costs of equipment,
maintenance and energy associated with individual packet processing in routers
(including repeated buffering and routing-table look-up) which is energy inefficient
\cite{RefWorks:3370} especially for large flows. In lower layers these will include for example cost of add-drop multiplexers (ADMs).

\item  Connection set-up, including recording and updating hash tables in flow-based routing, or the setup cost for an SDH or WDM paths in cases where those are used.

\item  Transmission.
\end{enumerate}
 In line with these three categories, we distinguish three size-based flow types:
\begin{enumerate}
\item  Mice: these are the small flows for which any flow setup cost will be more significant than any per-packet or per-byte costs. Their number is large and it may be optimal to route them in pre-set existing tunnels - possibly a lightpath. Their tunnels may be longer than shortest path (similar to busses that drop off and take up passengers along their routes).

\item  Elephants: these are large flows for which the flow setup cost will be insignificant. Their numbers are relatively small, so they justify complex flow setup and clear-down, possibly including the setup of a routed wavelength. Individual packet processing is avoided.

\item  Kangaroos: they are flows that are larger than the mice and smaller than the elephants where the connection set-up cost is neither negligible nor significantly larger than their data processing cost. It may be beneficial to route them based on the current IP architecture and to use shortest-hop-path routing to minimize the number of hops for them because their packets are treated individually at every router.
\end{enumerate}

 The best choice of boundaries between these flow-sizes, and also the best number of different sizes which should be distinguished has not yet been determined and will be the subject of investigation.



\input{costtests.tex}


\section{The Traffic Model} \label{traffic}

 Assume that the arrival process of the flows follow a Poisson process and that the sizes of the original flows are independent and Pareto distributed. As we assigned flows to layers based on their size, flow sizes in a given layer may follow a truncated Poisson distribution.



\subsection{Flow Size Distribution}\label{truncpareto}

 We assume that traffic in each layer is either continuous at a fixed rate, or is made up of a Poisson stream of flows, of rate $\lambda $, which have a truncated (or untruncated) Pareto distribution with shape parameter $\gamma $, with minimum size $\delta $ and maximum size $\Delta $. (We allow for $\Delta $ to be arbitrarily large ($\Delta =\infty $) so the case of untruncated Pareto distribution is included.) Assuming that flow sizes are measured in bits, the probability that a randomly selected flow is shorter than $t$ is:

\begin{equation} \label{truncparetoprob}
\left\{\begin{array}{ccc} {0,\quad \quad \quad \quad \; \; } & {} & {t<\delta ,\quad \quad } \\ {\frac{\left({\tfrac{\Delta }{\delta }} \right)^{-\gamma } -\left({\tfrac{t}{\delta }} \right)^{-\gamma } }{1-\left({\tfrac{\Delta }{\delta }} \right)^{-\gamma } } ,} & {} & {\delta <t<\Delta ,\; \; } \\ {1,\quad \quad \quad \quad \quad } & {} & {t\ge \Delta .\quad \quad } \end{array}\right.
\end{equation}
The mean bit-rate of such a Poisson stream of flows is:

\begin{equation} \label{truncparetorate}
\frac{\lambda \gamma \left(\delta ^{{\rm 1}-\gamma } -\Delta ^{{\rm 1}-\gamma } \right)}{(\gamma -{\rm 1})\left(\delta ^{-\gamma } -\Delta ^{-\gamma } \right)} 
=
\frac{\lambda \gamma \delta \left(1 -\left(\Delta\over\delta\right) ^{{\rm 1}-\gamma } \right)}{(\gamma -{\rm 1})\left(1 -\left(\Delta\over\delta\right) ^{-\gamma } \right)} 
.
\end{equation}

Since the rate of the corresponding untruncated process is $\lambda' = {\lambda\over 1 -\left(\Delta\over\delta\right) ^{-\gamma }}$, this last formula can be
interpreted as 
$$
\frac{\lambda' \gamma \delta \left(1 -\left(\Delta\over\delta\right) ^{{\rm 1}-\gamma } \right)}{(\gamma -{\rm 1})}
$$
which makes sense because the probability distribution of flows, wieghted according
to length, has complementary distribution function $\left(\Delta\over\delta\right) ^{{\rm 1}-\gamma }$ and $\frac{\lambda' \gamma \delta }{(\gamma -{\rm 1})}$ is the 
mean length of flows in the untruncated flow with the same rate for the flows
of the lower lengths.

\section{Fixed-point Algorithm  for Link Capacity Assignment}

 A simple and effective way to evaluate the performance of telecommunications networks is to use an approach involving {\em
fixed point iterations}. The behavior of traffic is affected by the capacity of the links, switches, and routers that it passes through, and also by the other traffic that uses the same resources at the same time. Given all the conditions which apply, relatively simple models can be used to predict the performance and behavior of one traffic stream. A fixed-point algorithm can then be used to predict the behavior and performance of the complete collection of traffic streams which share a network by successively replacing the traffic streams by streams which exhibit their behavior in the presence of the other traffic.

 Fixed-point algorithms have been used extensively in performance evaluation of telecommunications network. One example is the so-called Erlang fixed-point approximation (EFPA) method. It is based on decoupling the given system into independent server groups (subsystems) and computing blocking probability for each subsystem independently. EFPA was first proposed in \cite{cooper64} in 1964 for the analysis of circuit-switched networks and has been extensively used since then in network analyzes and design. See for example, \cite{rosberg2003} and references therein.

 In this paper our objective is not to estimate blocking probabilities but instead to estimate required capacities. Therefore, instead of iterating until convergence of loss probabilities has occurred, we adjust capacities at each iteration, and continue iterating until capacities have converged. Identifying conditions which ensure convergence is beyond the scope of this paper. Whereas in the EFPA the Erlang B formula is used to estimate loss, in the fixed-point iteration presented here simple formulae (e.g., mean traffic plus three standard deviations of traffic) are used to estimate the capacity required to achieve a certain target for loss on each link.

 Alternative approaches are used for link dimensioning based on the following link classifications:

\begin{enumerate}
\item  Links which carry only traffic representing permanent virtual links of a specified capacity (constant bitrate or peak rate allocated). There the required capacity is obtained by simply summing up the required capacities and rounding up to the next module size.

\item  Links where traffic is statistically random, but they are not the bottleneck for any of the streams that pass through them. Such links are typically located in the core network and their streams are bottlenecked typically at the access. For them, the required capacity is the mean traffic plus three standard deviations. The traffic variance is estimated by adopting a Poisson model for the number of active flows, in which the {\em rate} exhibited by each flow is assumed to be the rate of the \textit {maximin link} feeding traffic into this link, i.e. the maximum over all the traffic streams, of the speed of the bottleneck link for that traffic stream. If this maximin rate is denoted by $r_{mm} $, and the rate of the link is $r_{L} $, the variance of the rate on the link - using a Poisson model -- is approximated by $r_{mm}^{2} \left(r_{L} /r_{mm} \right)=r_{mm} r_{L} $.

\item  For each one of the remaining links, some traffic streams experience the link as their bottleneck link. Such links are typically located in the access network. The link behavior is governed by fair queueing, and therefore we adopt for them a utilisation target (which may be different in each layer).
\end{enumerate}

% \iflong
\input{dimtests.tex}
% \fi

\section{Analysis of Layered Networks} \label{layeredfpoint}

 The basic fixed-point algorithm described in the previous section
 can be extended to layered networks so long as we have a scheme for
 splitting traffic between layers.
 Splitting the type of traffic described in Section 2 is straightforward so long as the only criterion used for deciding which way to direct traffic is flow size.

\subsection{Layered Architecture}

 The most important principle of layered network
 architecture is that {\em each layer of a network employs services provided by layers
below to provide services to the layers above}. Sitting on top of this layer-cake of services are the demands from the users, which we refer to in this paper as {\em traffic streams}. Traffic from these user-generated traffic streams is carried by assigning it to {\em
paths} through the layer at the top. When there is a layer below this top layer, it is employed for one and only one reason: to implement links at the top layer. There are three distinct ways in which layer $n$ can implement a link between node {\em A} and node {\em B} at layer $n+{\rm 1}$:

\begin{enumerate}
\item  layer $n$ already has a link between {\em A} and {\em B} (either because \textit{n} = 0, and there is a physical link between {\em A} and {\em B}, or n$>$0 but layer n-1 has a link between {\em A} and {\em B}) and it simply passes on this service, at no {\em extra} charge (beyond transmission cost), to the layer above; when a link from {\em A} to {\em B} already exists, and is not over-utilized, this will always the best way to provide the link from {\em A} to {\em B} at layer $n+{\rm 1}$.

\item  layer $n$ does not have a link from {\em A} to {\em B} but it has a path from {\em A} to {\em B} which it can permanently package as a link, for layer $n+{\rm 1}$ (e.g. a lightpath at the optical layer can be viewed as a link at the IP layer).

\item  layer $n$ does not have a link from {\em A} to {\em B} but it can dynamically set up, as required, a path through its network from {\em A} to {\em B}.
\end{enumerate}

 There is usually a significant extra cost in making use of links as in Cases 2 and 3. In Case 2, this cost is mainly due to the fact that modularity requirements in layer $n$ will mean that the capacity of the path set up through this layer might be considerably more than is actually needed. In Case 3 the cost is due to the fact that every time a layer $n+{\rm 1}$ is set up, a significant cost is incurred. Modularity always restricts the use of paths through layer $n$, however in Case 3 we can assume that the path is fully utilized while the link is in use, so we can neglect this cost in Case 3. Since all the traffic carried by layer $n$ is derived from one of these three mechanisms, the traffic streams in layer $n$ correspond one-to-one with the links in layer $n+{\rm 1}$.

\subsection{Splitting }\label{splitting}

 Suppose the arrival rate of flows in a traffic stream is $\lambda $ with a range of flow sizes from $\delta $ to $\Delta $, and this is split on the basis of whether a flow is bigger or smaller than $D$. If the arrival rate of flows less than size $D$ is $\lambda _{{\rm 1}} $, then the stream containing these smaller flows will have the standard model, but with rate $\lambda _{{\rm 1}} $, and flows in the range $\delta $ to $D$.while the other stream will have a rate$\lambda -\lambda _{{\rm 1}} $ and a range flow sizes from $D$ to $\Delta $.

\subsection{Merging}

 The parameters of a merged stream that we need to choose are: (i) the flow arrival rate; (ii) the minimal flow size $\delta $; and (iii) the maximum flow size $\Delta $. (We assume that all traffic exhibits a common power law, with exponent $\gamma $.)  In order to determine the parameters of a merged traffic stream we adopt the principle that the flow rate of the merged stream should be the sum of the flow rates of the component streams, the maximum flow size should be the maximum of the maximum flow sizes of the component streams, and the mean bit-rate of the merged stream should be the sum of the bit-rates of the component streams. It follows that we have one free parameter, the minimum flow size, with which to ensure that the mean bit-rate is correctly matched. Since the mean of a Poisson stream of truncated (or untruncated) Pareto flows is given by \eqref{truncparetorate}, if the mean rate of such a traffic stream is m, the $\delta $ required to match this is the solution of:

\[m=\frac{\lambda \gamma \left(\delta ^{{\rm 1}-\gamma } -\Delta ^{{\rm 1}-\gamma } \right)}{(\gamma -{\rm 1})\left(\delta ^{-\gamma } -\Delta ^{-\gamma } \right)} {\rm .}\]
Rearranging this gives:

\[\delta =\frac{m(\gamma -{\rm 1})\left({\rm 1}-(\Delta /\delta )^{-\gamma } \right)}{\lambda \gamma ({\rm 1}-(\Delta /\delta )^{{\rm 1}-\gamma } )} ,\]
which can be used repeatedly to solve for $\delta $.


\section{Implementation}

 An algorithm for network design of a layered network was described and this algorithm has been
 implemented (see \cite{netml2,atnac06,netml4design}) and some preliminary experiments carried out.
 The experiments confirm that the network design algorithm converges quickly for very large networks.

\subsection{Scenarios}

Several scenarios have been explored with the fixed-point algorithm.

\section{Conclusion}

 We have outlined a unified optimization framework for a
 multi-layer network that facilitates choice of technologies,
 link dimensioning and design of virtual topology.
 More details on the software that is being developed and
 implementations for specific scenarios are available
 in \cite{netml2,atnac06,netml4design}.


\bibliographystyle{../erlang/IEEEtran}
%\bibliographystyle{plain}
\bibliography{../ofs/ofs,netml,OPC_bib,opt_top,all,wdm}
\end{document}
